1. Field of the Invention
The present invention relates to computerized cryptographic systems and methods for encrypting communications in a computer network or electronic communications system, and particularly to an RNS-based cryptographic system and method that forces an attacker to perform blind factorization of an unknown integer from which the residue number system is derived, and which may also include blind randomization to further secure the system from attack.
2. Description of the Related Art
In recent years, the Internet community has experienced explosive and exponential growth. Given the vast and increasing magnitude of this community, both in terms of the number of individual users and web sites, and the sharply reduced costs associated with electronically communicating information, such as e-mail messages and electronic files, between one user and another, as well as between any individual client computer and a web server, electronic communication, rather than more traditional postal mail, is rapidly becoming a medium of choice for communicating information. The Internet, however, is a publicly accessible network, and is thus not secure. The Internet has been, and increasingly continues to be, a target of a wide variety of attacks from various individuals and organizations intent on eavesdropping, intercepting and/or otherwise compromising or even corrupting message traffic flowing on the Internet, or further illicitly penetrating sites connected to the Internet.
Encryption by itself provides no guarantee that an enciphered message cannot or has not been compromised during transmission or storage by a third party. Encryption does not assure integrity due to the fact that an encrypted message could be intercepted and changed, even though it may be, in any instance, practically impossible, to cryptanalyze. In this regard, the third party could intercept, or otherwise improperly access, a ciphertext message, then substitute a predefined illicit ciphertext block(s), which that party, or someone else acting in concert with that party, has specifically devised for a corresponding block(s) in the message. The intruding party could thereafter transmit the resulting message with the substituted ciphertext block(s) to the destination, all without the knowledge of the eventual recipient of the message.
The field of detecting altered communication is not confined to Internet messages. With the burgeoning use of stand-alone personal computers, individuals or businesses often store confidential information within the computer, with a desire to safeguard that information from illicit access and alteration by third parties. Password controlled access, which is commonly used to restrict access to a given computer and/or a specific file stored thereon, provides a certain but rather rudimentary form of file protection. Once password protection is circumvented, a third party can access a stored file and then change it, with the owner of the file then being completely oblivious to any such change.
A residue number system (RNS) represents a large integer using a set of smaller integers, such that computation may be performed more efficiently. The RNS relies on the Chinese remainder theorem of modular arithmetic for its operation. In an RNS, the vector {p1, p2, . . . , pL} forms a set of moduli, referred to as the RNS “basis” β, in which the moduli {p1, p2, . . . , pL} are relatively prime with respect to one other. Using typical RNS convention, the product
      ∏          l      =      1        L    ⁢          ⁢      p    l  is represented as p and defines the dynamic range of the system. The vector {m1, m2, . . . mL} is the RNS representation of an integer M, which is less than P, where ml=<M>pl=M mod pl. Any integer m belonging to the set {0, . . . , P−1} has a unique representation in the basis β.
Further, the operations of addition, subtraction, and multiplication are defined over the set {0, . . . , P−1} as:C±D=(<cl±dl>pl, . . . ,<cL±dL>pL); and  (1)C×D=(<cl×dl>pl, . . . ,<cL×dL>pL).  (2)
Equations (1) and (2) illustrate the parallel carry-free nature of RNS arithmetic. The reconstruction of m from its residues {m1, m2, . . . , mL} is based on the Chinese Remainder Theorem:
                              M          =                                    〈                                                ∑                                      l                    =                    0                                    L                                ⁢                                                                  ⁢                                  <                                                            μ                      l                                        ⁢                                          m                      l                                                        ⁢                                      >                    pl                                    ⁢                                      P                    l                                                              〉                        P                          ,                                  ⁢        where                            (        3        )                                          P          =                                    ∏                              l                =                1                            L                        ⁢                                                  ⁢                          p              l                                      ;                            (        4        )                                                      P            l                    =                      P                          p              l                                      ;        and                            (        5        )                                          μ          l                =                                            〈                              P                l                                  -                  1                                            〉                                      p              l                                .                                    (        6        )            
The vector {m1, m2, . . . , mL}, where 0≦m′l<pl, is the Mixed Radix System (MRS) representation of an integer M less than P, such that
                    M        =                              m            1            ′                    +                                    m              2              ′                        ⁢                          p              1                                +                                    m              3              ′                        ⁢                          p              1                        ⁢                          p              2                                +          …          +                                    m              L              ′                        ⁢                                          ∏                                  l                  =                  1                                                  L                  -                  1                                            ⁢                                                          ⁢                                                p                  i                                .                                                                        (        7        )            It should be noted that, with regard to RNS equations (3) through (7), a change in any one of the residue values ml can have an effect on the whole number M.
Residue number systems are well known in computer systems. Residue number systems can convert the problem of arithmetic operations on a large integer to a series of simpler operations on small integers, with resulting efficiency in computation. However, although there have been some attempts to utilize residue number systems in cryptographic systems, these efforts are either still not computationally efficient or are vulnerable to attack.
Thus, a system and method for performing blind factorization-based residue number system encryption with blind randomization solving the aforementioned problems is desired.